All Questions
6 questions
0votes
0answers
102views
Understanding a remark on O(log d) ratio for Online Set Cover
In the paper "The Online Set Cover Problem" by Alon, Awerbuch, Azar, Buchbinder and Naor, they study an online version of the set cover problem in which elements arrive one by one and ...
- 649
2votes
0answers
80views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined. One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 649
2votes
0answers
181views
What is the competitive ratio of a $d$-way associative LRU cache?
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
- 9,548
5votes
0answers
181views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $...
- 1,601
17votes
3answers
556views
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
- 193
16votes
3answers
5kviews
Is there an online-algorithm to keep track of components in a changing undirected graph?
Problem I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
- 361
